package com.ljx.GetNumber;

/**
 * @author 李加喜
 * @Package com.ljx.GetNumber
 * @date 2021-12-14 9:52
 */

import java.util.*;

/**
 * 380 在O(1)下插入 删除 和获取随机元素
 */
public class RandomizedSet {
    public static void main(String[] args) {

    }
    List<Integer> nums;
    HashMap<Integer,Integer> map;
    Random rand = new Random();
    public RandomizedSet() {
        nums= new ArrayList<Integer>();
        map= new  HashMap<Integer,Integer>();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)){
            //在map已经存在就不能再进行插入
            return false;
        }
        map.put(val,nums.size());
        // 对于数组 进行存储
        nums.add(nums.size(),val);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)){
            //如果map不存在就不能再进行删除
            return false;
        }
        // 获取最后一个值
        Integer lastNum = nums.get(nums.size() - 1);
        // 先拿到 val 的索引
        Integer index = map.get(val);
        // 将最后⼀个元素对应的索引修改为 index  进行交换val和最后一个值
        // 直接设置 没有进行替换
        nums.set(index,lastNum);
        // 设置最后一个值的坐标是当前值的坐标
        map.put(lastNum,index);
        // list删除
        nums.remove(nums.size()-1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return nums.get(rand.nextInt(nums.size()));
    }
}
